Construire un graphe k-régulier - Corrigé

 Énoncé

1. Le cas  $k=2$ .
Soit un entier naturel non nul  $n$ . Peut-on construire un graphe connexe d'ordre $n$  dont tous les sommets sont de degré $k=2$ ?

2. Justifier que, pour tout entier  $k$  pair non nul, et tout entier naturel non nul  $n$ , on peut construire un graphe connexe d'ordre  $n$  dont tous les sommets sont de degré  $k$ .

3. Le cas  $k=3$ .
    a. Peut-on construire un graphe d'ordre 4 dont tous les sommets sont de degré  $k=3$  ?
    b. Peut-on construire un graphe d'ordre 5 dont tous les sommets sont de degré  $k=3$  ?
    c. Peut-on construire un graphe d'ordre 6 dont tous les sommets sont de degré  $k=3$  ?
    d. Donner une condition nécessaire sur  $n$  pour pouvoir construire un graphe d'ordre  $n$  dont tous les sommets sont de degré 3.
    e. Cette condition nécessaire est-elle suffisante ?

Solution

1. La réponse est oui, un polygone à  $n$  sommets figure un tel graphe.

2. Posons  $k=2p$ .
On peut reprendre le polygone précédent. Il suffit d'ajouter  $(p-1)$ boucles que nécessaire sur chaque sommet, ou de mettre  $p$  arêtes parallèles sur chaque côté du polygone.

3. a. Pour  $n=4$ , un rectangle avec ses diagonales figure un tel graphe.
    b. Pour  $n=5$ , la somme des degrés des sommets serait égale à  $15$ . Or, la somme des degrés est égale au double du nombre d'arêtes (nombre pair), donc c'est impossible.
    c. Pour  $n=6$ , on peut dessiner un hexagone avec 3 diagonales reliant des sommets distincts.
    d. Il faut que  $n$  soit pair, sinon comme dans le cas 3.b. la somme des degrés est impaire.
    e. Oui, cette condition est suffisante. Dans le cas où  $n=2p$  est pair, il suffit de tracer le polygone puis de tracer toutes les grandes diagonales (c'est-à-dire qu'on relie chaque sommet  $A_i$  pour  $i$  compris entre  $1$ et  $p$  au sommet  $A_{i+p}$ ).